package linkedlistskills;

import java.util.PriorityQueue;

public class solution23 {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null)
            return null;
        //设置一个虚拟头指针，接收弹出的最小node
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;

        //定义一个优先级队列，小顶堆
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(lists.length,(a,b)->(a.val- b.val));

        //先把lists当中的链表的head压入堆中
        //酱紫就快速选出三个链表中的最小值了
        for (ListNode head : lists) {
            priorityQueue.add(head);
        }

        while(priorityQueue.size()>0){
            ListNode node = priorityQueue.poll();
            if (node.next!=null){
                priorityQueue.add(node.next);
            }
            p.next = node;
            p = p.next;
        }

        return dummy.next;
    }
}
